# LeetCode 516、最长回文子序列
# 一、题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长回文子序列（ LeetCode 516 ）：https://leetcode-cn.com/problems/longest-palindromic-subsequence
class Solution {
public int longestPalindromeSubseq(String s) {
// 获取字符串 s 的长度
int length = s.length();
// 设置数组 dp，用来存储字符串 s 的最长的回文子序列的长度
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
// dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
// dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
// i 最大值为 length - 1
int[][] dp = new int[length][ length];
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
// dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
// dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的最长的回文子序列的长度
// 此时，这个区间的字符只有一个，最长的回文子序列的长度为 1
for (int i = 0; i < length; i++) {
dp[i][i] = 1;
}
// i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
// 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
for (int i = length - 1; i >= 0; i--) {
for( int j = i + 1 ; j < length ; j++ ){
// 如果发现 s.charAt(i) == s.charAt(j)
if (s.charAt(i) == s.charAt(j)) {
// dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
// dp[i][j] 表示字符串 s 第 i + 1 个字符和字符串 s 第 j - 1 个字符之间的最长的回文子序列的长度
// 由于扩充的两个字符相等，意味着最长的回文子序列的长度加 2
dp[i][j] = dp[ i + 1 ][ j - 1 ] + 2;
}else{
// 字符区间 s[i..j] 里最长回文子序列的长度
// 1、去掉头以后的区间的最长的回文子序列的长度，即 dp[i + 1][j]
// 2、去掉尾以后的区间的最长的回文子序列的长度，即 dp[i][j - 1]
// 二者取最大值
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
// 最右上角的值就是结果
return dp[0][length - 1];
}
}
# **2、**C++ 代码
class Solution {
public:
int longestPalindromeSubseq(string s) {
// 获取字符串 s 的长度
int length = s.length();
// 设置数组 dp，用来存储字符串 s 的最长的回文子序列的长度
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
// dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
// dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
// i 最大值为 length - 1
auto dp = vector < vector < int>> ( length ,vector<int> ( length ));
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
// dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
// dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的最长的回文子序列的长度
// 此时，这个区间的字符只有一个，最长的回文子序列的长度为 1
for (int i = 0; i < length; i++) {
dp[i][i] = 1;
}
// i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
// 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
for (int i = length - 1; i >= 0; i--) {
for( int j = i + 1 ; j < length ; j++ ){
// 如果发现 s.charAt(i) == s.charAt(j)
if (s[i] == s[j]) {
// dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
// dp[i][j] 表示字符串 s 第 i + 1 个字符和字符串 s 第 j - 1 个字符之间的最长的回文子序列的长度
// 由于扩充的两个字符相等，意味着最长的回文子序列的长度加 2
dp[i][j] = dp[ i + 1 ][ j - 1 ] + 2;
}else{
// 字符区间 s[i..j] 里最长回文子序列的长度
// 1、去掉头以后的区间的最长的回文子序列的长度，即 dp[i + 1][j]
// 2、去掉尾以后的区间的最长的回文子序列的长度，即 dp[i][j - 1]
// 二者取最大值
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
// 最右上角的值就是结果
return dp[0][length - 1];
}
};
# 3、Python 代码
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# 获取字符串 s 的长度
length = len(s)
# 设置数组 dp，用来存储字符串 s 的最长的回文子序列的长度
# dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
# dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
# dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
# i 最大值为 length - 1
dp = [[0] * (length) for _ in range(length)]
# dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
# dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
# dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的最长的回文子序列的长度
# 此时，这个区间的字符只有一个，最长的回文子序列的长度为 1
for i in range( 0 ,length) :
dp[i][i] = 1
# i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
# 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
for i in range( length - 1 , -1, -1) :
for j in range( i + 1 ,length ) :
# 如果发现 s.charAt(i) == s.charAt(j)
if s[i] == s[j]:
# dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
# dp[i][j] 表示字符串 s 第 i + 1 个字符和字符串 s 第 j - 1 个字符之间的最长的回文子序列的长度
# 由于扩充的两个字符相等，意味着最长的回文子序列的长度加 2
dp[i][j] = dp[ i + 1 ][ j - 1 ] + 2
else:
# 字符区间 s[i..j] 里最长回文子序列的长度
# 1、去掉头以后的区间的最长的回文子序列的长度，即 dp[i + 1][j]
# 2、去掉尾以后的区间的最长的回文子序列的长度，即 dp[i][j - 1]
# 二者取最大值
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
# 最右上角的值就是结果
return dp[0][length - 1]